"""
LevenshteinSimilarity
具体的一个计算实现的方法，
这是一个传统的计算相似度的方法
"""

from nl2sql.similarity.base import SimilarityBase


class LevenshteinSimilarity(SimilarityBase):
    """
    Levenshtein（编辑距离）算法实现
    """

    def get_similarity_score(self, str1: str, str2: str) -> float:
        # 计算编辑距离
        def levenshtein(a: str, b: str) -> int:
            n, m = len(a), len(b)
            dp = [[0] * (m + 1) for _ in range(n + 1)]
            for i in range(n + 1):
                for j in range(m + 1):
                    if i == 0:
                        dp[i][j] = j
                    elif j == 0:
                        dp[i][j] = i
                    elif a[i - 1] == b[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1]
                    else:
                        dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
            return dp[n][m]

        # 计算相似度：1 - (编辑距离 / max 长度)
        dist = levenshtein(str1, str2)
        return 1 - dist / max(len(str1), len(str2))

    pass


if __name__ == '__main__':
    ls = LevenshteinSimilarity()
    print(ls.find_best_match('南航', ['中国南方航空', '中国东方航空', '中国国际航空']))
